package _动态规划系列._打家劫舍;

/**
 * @Author: 吕庆龙
 * @Date: 2020/4/1 20:20
 * <p>
 * 功能描述:
 */
public class Summary_0213 {

    /**
     * dp[i]: 从第i间房子开始往后打劫房子(不包括第i间)，最多能抢到的钱
     * 这个的思路才是从前往后抢的
     */
    public int rob(int[] nums) {
        int n = nums.length;
        int[] dp_1 = new int[n + 1];

        if (n == 0)
            return 0;

        if (n == 1)
            return nums[0];

        //第1间房子到第n -1间
        dp_1[n] = 0;
        dp_1[n - 1] = 0; //因为这种情况只能抢到第n-1间,所以第n间就抢不到了
        for (int i = n - 2; i >= 0; i--) {
            dp_1[i] = Math.max(dp_1[i + 1]  //不抢
                    , dp_1[i + 2] + nums[i]);//抢
        }

        int[] dp_2 = new int[n + 2];

        //第2间房子到第n间
        dp_2[n] = 0;
        dp_2[n + 1] = 0;
        for (int i = n - 1; i >= 1; i--) {
            dp_2[i] = Math.max(dp_2[i + 1]  //不抢
                    , dp_2[i + 2] + nums[i]);//抢
        }

        return Math.max(dp_1[0], dp_2[1]);
    }
}
